package week_03;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 329. 矩阵中的最长递增路径
 * 给定一个m x n 整数矩阵matrix ，找出其中 最长递增路径 的长度。
 * <p>
 * 对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
 * 输出：4
 * 解释：最长递增路径为[1, 2, 6, 9]。
 * 示例 2：
 * <p>
 * <p>
 * 输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
 * 输出：4
 * 解释：最长递增路径是[3, 4, 5, 6]。注意不允许在对角线方向上移动。
 * 示例 3：
 * <p>
 * 输入：matrix = [[1]]
 * 输出：1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LongestIncreasingPath_BFS_329 {
    int m;
    int n;
    int[] dist;
    int ans;
    //                U,L,R,D
    int[] dx = new int[]{-1, 0, 0, 1};
    int[] dy = new int[]{0, -1, 1, 0};
    List<List<Integer>> edges;
    int[] indegs;

    public int longestIncreasingPath(int[][] matrix) {
        // 使用bfs 搜索
        // 1.建边，初始化度数

        m = matrix.length;
        n = matrix[0].length;
        dist = new int[m * n];
        indegs = new int[m * n];
        edges = new ArrayList<>();
        for (int i = 0; i < m * n; i++) {
            edges.add(new ArrayList<>());
            System.out.println(dist[i]);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    // 判断边界 是否越界
                    if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
                    // 遍历上下左右前后 四个新点建边
                    if (matrix[nx][ny] > matrix[i][j]) {
                        addEdges(nums(i, j), nums(nx, ny));
                    }
                }
            }
        }
        // 2.topSort用bfs拓扑排序减边
        topSort(matrix);
        // 3.迭代答案dist[] 找到最大的步数边返回答案
        ans = 0;
        for (int i = 0; i < dist.length; i++) {
            System.out.println(i+":"+dist[i]+":"+ans);
            ans = Math.max(ans, dist[i]);
        }
        return ans;
    }

    private void addEdges(int u, int v) {
        edges.get(u).add(v);
        indegs[v] += 1;
    }

    private int nums(int i, int j) {
        return i * n + j;
    }


    private void topSort(int[][] matrix) {
        Deque<Integer> deque = new LinkedList<>();
        // 0度点入队列
        for (int i = 0; i < indegs.length; i++) {

            if (indegs[i] == 0) {
                dist[i] = 1;
                deque.add(i);
            }
        }
        // while循环广搜
        while (!deque.isEmpty()) {
            int u = deque.getFirst();
            deque.removeFirst();
            //取当前节点的边
            for (int edge : edges.get(u)) {
                System.out.println("edge:"+edge+":"+dist[edge]+":"+dist[u] + 1);
                dist[edge] = Math.max(dist[edge], dist[u] + 1);
                indegs[edge] -= 1;
                if (indegs[edge] == 0) {
                    deque.add(edge);
                }
            }
        }

    }
}
